Additive number

Time: O(N^3); Space: O(N); medium

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers.

Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number.

Note:

  • Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: num = “112358”

Output: True

Explanation:

  • The digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

  • 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

Input: num = “199100199”

Output: True

Explanation:

  • The additive sequence is: 1, 99, 100, 199.

  • 1 + 99 = 100, 99 + 100 = 199

Constraints:

  • num consists only of digits ‘0’-‘9’.

  • 1 <= len(num) <= 35

Follow up:

  • How would you handle overflow for very large input integers?

[1]:

class Solution1(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        def add(a, b):
            res, carry, val = "", 0, 0
            for i in range(max(len(a), len(b))):
                val = carry
                if i < len(a):
                    val += int(a[-(i + 1)])
                if i < len(b):
                    val += int(b[-(i + 1)])
                carry, val = val // 10, val % 10
                res += str(val)
            if carry:
                res += str(carry)
            return res[::-1]


        for i in range(1, len(num)):
            for j in range(i + 1, len(num)):
                s1, s2 = num[0:i], num[i:j]
                if (len(s1) > 1 and s1[0] == '0') or \
                   (len(s2) > 1 and s2[0] == '0'):
                    continue

                expected = add(s1, s2)
                cur = s1 + s2 + expected
                while len(cur) < len(num):
                    s1, s2, expected = s2, expected, add(s2, expected)
                    cur += expected
                if cur == num:
                    return True
        return False

[3]:

s = Solution1()

num = "112358"
assert s.isAdditiveNumber(num) == True

num = "199100199"
assert s.isAdditiveNumber(num) == True

num = "1"
assert s.isAdditiveNumber(num) == False